package cn.walls1717.leetcode.array;

import cn.walls1717.leetcode.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 283. 移动零
 * 力扣地址：https://leetcode-cn.com/problems/move-zeroes/
 *
 * @author walls1717
 * @since 2022-05-01
 **/
public class T283 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes2(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 暴力破解
     * 使用冒泡排序，遇到 0 直接冒泡到最后
     * 时间复杂度较高
     *
     * @param nums 数组
     */
    private static void moveZeroes(int[] nums) {
        int n = nums.length - 1;
        int last;
        do {
            last = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] == 0) {
                    AlgorithmUtil.swap(nums, i, i + 1);
                    last = i;
                }
            }
            n = last;
            System.out.println(n);
        } while (n != 0);
    }

    /**
     * 双指针法
     *
     * @param nums 数组
     */
    private static void moveZeroes2(int[] nums) {
        // 设置快慢指针
        int fastIndex = 0;
        int slowIndex;
        // 快指针找到不为 0 的元素给慢指针
        // 循环结束，慢指针位置就是不含 0 的数组大小
        for (slowIndex = 0; fastIndex < nums.length; ++fastIndex) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex] = nums[fastIndex];
                ++slowIndex;
            }
        }
        // 只需要将后面的元素全部置为 0 即可
        for (; slowIndex < nums.length; ++slowIndex) {
            nums[slowIndex] = 0;
        }
    }
}
